A vibration sensor outputs an analog signal with a peak-to-peak voltage of 5V at a frequency of 100 Hz.

(a) What should be the minimum sampling frequency, so that no information is lost during the digitization process? 答：使用奈奎斯特定理，无损塑模出原始模拟信号需要频率为2f，也即100*2=200Hz

(b) Suppose a resolution of 0.025V is required to detect an interesting event. What should be the resolution of the ADC in terms of bits to convert the analog signal to a digital signal? 答：我们有公式 Q = E p p 2 m Q=\frac{E_{pp}}{2^{m}} Q=2mEpp​​ 其中， Q Q Q是分辨率， E p p E_{pp} Epp​是波峰到波谷之间的差，m是表示这个模拟量需要多少bit。 根据上述公式，我们计算 2 m = 5 − ( − 5 ) 0.025 = 400 2^{m}=\frac{5-(-5)}{0.025}=400 2m=0.0255−(−5)​=400 因此我们至少需要9bit才能表示该模拟量。

While they are not the most energy-efficient solutions, microcontrollers are the predominant processors in wireless sensor networks. Explain some of the reasons.

答：Microcontrollers offer greater programming flexibility compared with the other types of smallscale processors; hence, they are useful for many applications. 微控制器的优点：结构紧凑，体积小，功耗低和低成本，使其适合构建计算不太密集的独立应用。同时使用C语言为编程，使用户能够不必了解过多底层的具体细节。 微控制器相较其他小规模处理器的优点就是它提供了更加方便灵活的编程，使用高级语言编程。

Explain the reason why using the Von Neumann architecture is not efficient for a wireles ssensor node.

答：In the Von Neumann architecture, there is a single memory space for data as well as program code and a single bus interfaces the memory unit with the processor. This means each data and instruction transfer requires a separate cycle, as a result of which computation is slow in lowscale processing subsystems. 冯诺依曼体系结构中，指令与数据存储在一起，而主存与处理器之间只有一个简单的总线用于传输数据，因此每次数据传输都花费一个独立的串行时钟计时。这样工作相当低效。 因此WSN采用Super-Harvard (SHARC) 超-哈佛结构，其中，IO流与数据存储器件之间使用DMA机制，不需要处理器控制实现数据直接存取，加快了处理速度。

Why are parallel busses not desirable in a wireless sensor node?

答：Parallel busses require large space. This is difficult to accommodate in small sensor nodes. 体积限制

Explain the basic similarities and differences between a FPGA and an ASIC.

答： Difference between ASICs and FPGAs mainly depends on costs, tool availability, performance and design flexibility. Table 3.1 summarized some of their differences.

Explain some of the distinct features of the SuperHarvard architecture. (a) It provides an internal instruction cache to store frequently needed instructions.（指令cache存储常用指令） (b) Program memory can be used to store data. (c) Direct data streaming from an external hardware into the data memory through an I/O controller is possible.（使用DMA）

Compare the following scheduling mechanisms: (a) FIFO scheduling (b) sorted queue (c) round-robin

答： (a) FIFO scheduling In a FIFO scheduling mechanism a task is processed based on the first-in-first-out principle.

(b) Sorted queue In a sorted queue scheduling mechanism, tasks in a queue are first sorted according to a set criterion, for example, based on their length.

(c) Roundrobin In roundrobin schedulingmechanism, timemultiplexing is used to divide time fairly among competing tasks. The execution time is divided into several slots and each task is executed in a slot. When the slot is due, the task is set on hold and the next task is executed. This way, all tasks progress together towards their completion.

What are interrupts and interrupt handlers?

答：An interrupt is an asynchronous signal (event) and is generated by a hardware or software componentwhich requires immediate handling.When the processing subsystemreceives an interrupt event, it transfer control to an interrupt handler, also called an interrupt service routine (ISR). An interrupt handler is a callback subroutine which is called by the operating system when an interrupt event is received. Interrupt handlers should register for the interrupt types they are interested in.

Why do most operating systems in wireless sensor networks define a kernel?

答：A monolithic kernel with a small finger print enables dynamicmodule update and dynamic reprogramming.

Explain the difference between configuration components and modules in TinyOS.

答：A configuration component describes how different modules are interconnected to build an executable service or application, whereas a module is an implementation of an interface.

配置组件描述可执行的服务与应用之间的关系，而模块是一个接口的具体实现。

Explain the difference between eventbased and threadbased operating systems. Discuss some of the advantages and disadvantages of the two approaches in the context of wireless sensor networks.

答： In eventbased programming： interaction between processes is based on events and event handlers. Tasks are executed to completion, unless they are interrupted by events. This way concurrency is supported and execution is efficient. Since only one task is executed at a time, longduration tasks may block shortduration tasks, but this problem can be overcome by using a sorted queue scheduling.

In multithreaded programming： multiple threads run concurrently. Threads can be suspended ensuring nonblocking operation. However, thread management introduces resource overhead on the operating system.

基于事件的并发处理机制更加高效，正在运行的事件只能能被其他事件打断。虽然可能会出现饥饿现象，但可通过sorted queue调度算法避免。 线程会挂起以避免阻塞，但线程管理会带来额外开销。

Explain the following concepts in TinyOS: (a) commands (b) tasks (c) events

答： (a) Commands： Commands are nonblocking requests for service. (b) Tasks： Tasks are monolithic processes that should be executed to completion (c) Events： An event is an occurrence of interest outside of a process and prompts the process to act (or handle the event).

What are the advantages and disadvantages of contentionfree and contentionbased medium access strategies? Can you think of scenarios where one would be preferable over the other?

答： Contentionfree medium access strategies avoid collisions by ensuring that when one device transmits, all other devices that could interferewith the reception of the transmitted data remain silent. Avoiding collisions can have positive impacts on communication latency and throughput. Most contentionfree approaches are based on schedules, indicating exactly when a node can transmit or must listen. This also facilitate power management strategies, e.g. using such a schedule, a device knows exactly when it can power down its radio. On the other hand, contentionbased mediumaccess strategies do not avoid collisions, but instead provide mechanisms to recover from collisions. An advantage of such a strategy is that a device does not have to wait (and delay), but instead can transmit immediately. In networks with lowtraffic loads, this approachmay result in lower latencies.A contentionbased strategy may also be easier to implement, since no schedules are required. Besides the potential collisions (which may lead to increased latency and reduced throughput), it may bemore difficult to implement duty cycle techniques in a network using a contentionbased MAC protocol.

Contentionbased access strategies may be preferable in networks with light traffic loads and unpredictable (or sporadic) traffic patterns. Contentionfree access schemes are useful when the traffic is predictable (e.g. sensor nodes periodically reporting their sensed data) and when it is important to maximize the sleep times of the wireless radios.

冲突避免的MAC协议确保有设备正在传输时，共用信道的其他设备保持沉默，冲突避免对信道延迟与吞吐量有积极作用，这通常依赖于调度算法实现。同时设备必须监听信道，这促进了电源管理策略的产生。 基于冲突的MAC协议不能避免冲突的发生，但提供从冲突中恢复的算法。在一个设备正在传输时，其他设备不必一定要一直等待（但也不是立即传输），在低负载的网络中，这会导致更低的时延。同时由于不需要额外的调度算法，这种协议更易实现。 基于冲突的协议一般更适合低负载、数据量不可预测的网络。 基于冲突避免的协议更适用于高负载、数据量可预测的网络，同时它还能最大化无线广播的睡眠时间，存在更节能的协议。

What are “hidden terminals” and how do they affect the performance of wireless sensor networks? When two sender devices A and B are both able to reach a third device C, but they are not able to reach each other, the situation may occur where both A and B attempt to transmit to C at the same time, unaware of the collision occurring at C. That is, A and B are hidden from each other. The consequences of such collisions are the need for recovery mechanisms, increased delays, and reduced throughput. A MAC protocol has to be able to either recover from such a collision or prevent such collisions by preventing devices A and B from transmitting to C at the same time.

当C在A和B传输的覆盖范围，但A、B彼此不在对方的覆盖范围内，A、B可能会同时向C发起传输请求，这意味着原本A、B能感知到对方正在发送数据，自己应当保持沉默。但由于覆盖范围原因，二者并无法感知到对方正在传输数据，因此发生的碰撞问题。 幸运的是，这个问题可以被RTS/CTS机制解决。

Consider the network topology in Figure 6.1, where circles indicate the communication and interference range of each node, i.e. each node can hear the immediate neighbors to the left and right. Assume that RTS/CTS is not being used. (a) Node B currently sends to node A and node C wants to send to node D. Is node C allowed to do so (i.e., can it do so without causing a collision) and will it decide to do so?

答：Yes, node C will not cause a collision at node A. However, since node C can hear node B’s transmission, it will not transmit. C本可以传输不产生冲突，但它不会传输。 这里是一个暴露终端问题，C听到了B的传输请求，它不知道对方的目的端与自己的目的端不同，因此等待直至该传输完成，在B向A的传输期间，C将会保持静默。

(b) Node C sends to node B and node E wants to send to node D. Is E allowed to do so and will it do so?

答：Node E’s transmission will not interfere with C’s transmission to B, however its own transmission to D will not succeed since it will collide with node C’s transmission. Node E is unaware of node C’s transmission and therefore it will begin its transmission. 如果发送，应当会发生冲突，由于隐终端问题，E未侦测到C的传输，因此会发送从而产生冲突。

(c) Node A sends to node B and node D sends to node C. Which other nodes are allowed to send at the same time?

答：实际E发送给F应当无冲突，而E在D的广播范围内，因此F若给E发送会产生冲突。由于存在暴露终端问题，E检测到D在发送，将不会向F发送，保持静默。同时，由于存在隐终端问题，F未检测到D在发送，因此会给E发送数据。

(d) Node A sends to node B and node E sends to node F. Which other nodes are allowed to send at the same time?

答：由于隐终端问题，C将被允许向B、D发送，但C向B发送的数据会产生冲突。 由于暴露终端问题，D本可以给C发送消息而不产生冲突，但D由于探测到E在发送，因此将保持静默。

Describe the problems in using CSMA as medium access control mechanism in a WSN.

答：CSMA does not address the hiddenterminal problem and collisions can be costly, particularly if the transmitted frames are large. Neighboring nodes also do not know how long transmissions will take, making it difficult to decide whether to power down a wireless radio (and for how long).

CSMA不能解决隐藏终端的问题，并且如果发生冲突可能代价高昂，尤其是在传输的帧较大的情况下。 相邻节点也不知道传输将花费多长时间，这使得很难决定是否关闭无线电（以及持续多长时间）。

In a CSMA/CA network, nodes use a random delay before accessing the medium. Why is this being done?

答：In CSMA, nodes can access the wireless medium immediately after it has been sensed idle. CSMA/CA is a variation of the CSMA protocol, where the number of collisions are reduced by randomly delaying medium access. That is, a node with a short random delay may access the medium sooner than a node choosing a larger random delay. The node with the larger delay will therefore overhear the transmission of its neighbor and it will not initiate a transmission, thereby avoiding a collision.

在CSMA中，节点可以在感知到信道空闲后立即访问无线介质。 CSMA / CA是CSMA协议的一种变体，其中通过等待一个随机时间再访问信道来减少冲突次数。 当一个节点在结束传输后，其它节点监测到信道空闲，此时若都直接开始发送，则多个节点都开始传输，产生冲突。因此，需要每个节点等待一个随机时间，随机时间长的节点将会监测到随机时间短的节点已经开始发送，从而避免一个节点发送结束后多个节点同时启动的情况。

How does MACAW extend MACA and what is the purpose of the additional control messages?

答：In MACAW, a receiver responds with an acknowledgment (ACK) frame to indicate a successful reception of the data frame. This allows neighboring nodes to learn that the transmission has finished and that the channel has become available. In addition, a node transmitting an RTS frame also transmits a Data Sending (DS) frame immediately after receiving a CTS frame for its RTS frame. A node overhearing the RTS frame, but not the corresponding CTS frame, has now confirmation that the reservation has succeeded and that it must remain silent to not interfere with the transmission.

MACAW是专用于无线信道的MACA协议，它对MACA协议做了一些改进： （1）接收节点在接受到数据后，会回复一个ACK帧响应，表示收到了数据帧。 （2）发送RTS的节点在收到CTS的响应后，将会广播一个DS帧，其中附上了额外信息，通知邻居节点自己将要发送数据的时间，邻居节点将会在这段时间内保持静默。

Why is the IEEE 802.15.4 standard preferable over the IEEE 802.11 standard for most wireless sensor networks?（对于大多数无线传感器网络，为什么 IEEE 802.15.4 标准优于 IEEE 802.11 标准？）

答：The IEEE 802.15.4 standard was created specifically for lowpower devices, with much lower data ranges compared to IEEE 802.11 and channels in the 868 MHz, 915 MHz, and 2.45 GHz ranges. Its focus on low power and low data rates much better meets the demands of wireless sensor networks than the IEEE 802.11 standard.

IEEE 802.15.4 标准专为低功耗器件创建，与 IEEE 802.11 相比，其数据范围和 868 MHz、915 MHz 和 2.45 GHz 范围内的通道的数据范围要低得多。与 IEEE 802.11 标准相比，其专注于低功耗和低数据速率，更符合无线传感器网络的需求。

Describe how the design of the MAC protocol affects the energy efficiency of a sensor node. 答：Since the MAC protocol determines when a node may access a wireless channel for communication, its design determines when and for how long a node can power down its wireless radio to preserve energy. Some MAC protocols require nodes to be awake continuously to ensure that no messages are missed. Other protocols use schedules that determine exactly when a node must stay awake, allowing a node to sleep without the risk of losing messages. Other MAC protocol characteristics affecting energy efficiency include packet header overheads, reliability features (such as retransmission and error controlmechanisms), and the number (and sizes) of controlmessages exchanged between nodes. 由于 MAC 协议确定节点何时可以访问无线信道进行通信，因此其设计决定了节点何时以及何时关闭其无线无线电电源以节省能源。某些 MAC 协议要求节点持续唤醒，以确保不会遗漏任何消息。其他协议使用计划，这些计划准确确定节点何时必须保持唤醒状态，从而允许节点处于睡眠状态，而不会丢失消息。影响能效的其他 MAC 协议特征包括数据包头开销、可靠性功能（如重传和错误控制机制）以及节点之间交换的控制消息的数量（和大小）。 类似NAV机制与MACAW的DS帧机制都能确定节点应当何时访问信道，其他时间节点都可处于睡眠状态以节省能量。

The TRAMA protocol is an example of a contention-free MAC scheme. Answer the following questions about TRAMA.

TRAMA协议指的是Traffic-Adaptive Medium Access，它基于每个节点的流量信息，使用分布式选举方案来确定何时允许节点传输。这有助于防止为没有流量的节点分配时间槽（导致吞吐量增加），并允许节点确定它们何时可以空闲，并且不必侦听通道（提高了能效）。 邻域协议 （NP） 用于在相邻节点之间传播单跳邻居信息，从而允许它们获取一致的双跳拓扑信息。在随机访问间隔期间，节点通过在随机选择的时间槽中传输来连接网络。在这些时间槽中传输的数据包用于通过携带一组添加和删除的邻居来收集邻域信息。如果没有发生任何更改，这些数据包将充当"keeplive"消息。通过收集此类更新，节点知道其自己的单跳邻居的单跳邻居，从而获取有关其双跳邻域的信息。

(a) What are the advantages and disadvantages of the TRAMA protocol (compared to contention-based protocols)?

答：TRAMA reduces the probability for collisions and dynamically determines when a node is allowed to transmit (based on traffic), thereby increasing the throughput. Since TRAMA uses a timeslotted channel, it allows nodes to determine when they must stay awake and when they can enter lowpower sleep modes. Nodes must be awake during the randomaccess intervals. As with other contentionfree protocols, communication in TRAMA may experience larger latencies than in contentionbased protocols since a node must wait for its scheduled slot before it can begin transmission.

TRAMA 降低了冲突的可能性，并动态确定何时允许节点传输（基于流量），从而提高吞吐量。由于 TRAMA 使用时隙通道，它允许节点确定何时必须保持清醒以及何时可以进入低功耗睡眠模式。节点必须在随机访问间隔期间唤醒。与其他无争用协议一样，TRAMA 中的通信可能会遇到比基于争用的协议更大的延迟，因为节点必须等待其计划插槽才能开始传输。 冲突少，因此吞吐量大；节点可确定何时空闲，因此节能；但必须分配到时间槽才能发送数据，因此延迟更高。

(b) What is the difference between transmission slots and signaling slots?

答：The time slots of the scheduledaccess intervals are assigned to individual nodes (for contentionfree transmission) while signaling slots are used for random medium access (contentionbased communication).Nodes can join a network by transmitting during randomly selected slots in the randomaccess intervals.

transmission slots分配给单个节点用于无争用传输，而signaling slots用于随机介质访问（基于争用的通信）。节点可以通过在随机访问间隔中随机选择插槽传输来加入网络。

© What is the purpose of the NP component?

答：The Neighbor Protocol (NP) is responsible for propagating onehop neighbor information among neighboring nodes, allowing these nodes to obtain consistent twohop topology information.

Neighbor Protocol（NP） 用于在相邻节点之间传播单跳邻居信息，从而允许它们获取一致的双跳拓扑信息。

Discuss the cluster head election policy in the LEACH protocol and explain how LEACH can consider available energy on each node in this election process. What is the problem with this energyaware election policy? Further, LEACH uses TDMA within a cluster;explain the advantages and disadvantages of this approach.

LEACH协议即Low-Energy Adaptive Clustering Hierarchy协议，这是一个动态选择集群头的协议，在一些情况下，由集群头收集整理数据后再集中发送给数据中心，要比多个分散节点分别给数据中心发送数据更合适。 由于群集头负责协调群集活动和将数据转发到基站，因此与其他传感器节点相比，其能量需求将大得多。因此，LEACH 在传感器节点之间轮换群集头责任，以均匀分配能量负载。

答：In the LEACH protocol, a node independently decides whether it becomes a cluster head or not. This decision is based on how long it has been that it has served as cluster head, i.e. a node is more likely to become a cluster head if it has not assumed this responsibility for a long time. The goal of this job rotation is to balance the workload among nodes and to prevent that a cluster head depletes its battery prematurely. Equation 6/6 in the book shows an approach to balance the cluster head responsibility among nodes based on the actual current energy levels of the nodes. The problem with this approach is that each node must know (or at least estimate) the sum of all nodes’ energy levels. Using TDMA within a cluster provides contentionfree communication between sensor nodes and cluster heads. To limit interference among clusters, LEACH uses direct sequence spread spectrum techniques. Using TDMA within a cluster has the “usual” advantages and disadvantages (e.g. with respect to latency, throughput, duty cycles) compared to contentionbased techniques.

在 LEACH 协议中，节点独立决定它是否成为集群头。此决策基于它担任群集头的时间，即如果节点长时间未承担此责任，则更有可能成为集群头。此工作轮换的目标是平衡节点之间的工作负载，并防止群集头过早耗尽电池。 同时也有基于当前剩余能量分配集群头责任的方法。此方法的问题是，每个节点必须知道（或至少估计）所有节点的能量水平的总和。在集群中使用 TDMA 可在传感器节点和群集头之间提供无争用的通信。为了限制集群之间的干扰，LEACH使用直接序列扩频技术。与基于争用的技术相比，在集群中使用 TDMA 具有"通常"的优点和缺点（例如，在延迟、吞吐量、占空比方面）。 延迟可能较高，吞吐量不高，空闲信道可能被浪费。但时间槽可以根据动态TDMA的需求分配，切换代价较小。

What is the “early sleeping problem” and how does TMAC address this problem? 答：The problem is that a node losing the medium, but wishing to transmit after the current transmission has completed will staywake, while its intended receiver may be unaware of the node’s intent and will go to sleep. Therefore, the future request to send technique adds another control message, the FTRS packet, which is sent by the node planning a future transmission after it has observed the CTS from the receiving node of the current transmission. This FTRS packet will be seen by its intended receiver.

一个节点在传输完成后会失去信道控制权，但希望在当前传输完成后传输将保持唤醒，而其预期的接收节点可能不知道该节点的意图，并将进入睡眠状态。因此，发送节点可以发送另一个控制消息 FTRS 数据包，该数据包从当前传输的接收节点观察了CTS。此 FTRS 数据包将由其预期的接收节点看到。

The previous chapter talked about MAC protocols, while this chapter introduced routing protocols. Can you think of examples how the choice of MAC protocol affects the design, performance, and efficiency of the routing protocol?

答：The choice of MAC protocol can have several impacts on the design or performance of a routing protocol. For example, communication latencies are determined by the type of MAC protocol (contentionfree versus contentionbased) and on the use of duty cycling at the link layer. The MAC protocol is responsible for error recovery due to collisions and other interferences, i.e. the routing layer may decide to rely on the MAC layer for reliable communications or it may implement its own mechanisms to ensure reliability.Some approaches discussed in the chapter on MAC protocol rely on a tight integration of MAC and routing protocols, e.g. the LEACH protocol (which uses clusters that affect both medium access and routing decisions) or the DMAC protocol (which uses fixed routes from sensor nodes to a sink).

通信时延由 MAC 协议的类型（无争用或基于争用）和链路层的占空比决定。 网络层将基于MAC层是否提供可靠性保障来决定，是否由自己提供可靠性保障。 同时还有一些协议依赖于 MAC 和路由协议的紧密集成。例如 LEACH 协议（使用影响中等访问和路由决策的集群）或 DMAC 协议（使用来自传感器节点到接收器）。

What is the difference between a proactive routing protocol and a reactive routing protocol? Name at least two examples for each category. （主动路由协议和被动路由协议之间的区别是什么？为每个类别至少命名两个示例。）

答：A proactive routing protocol establishes and maintains routing information (typically in the formof tables) before it is actually needed. This allows a node to quicklymake routing decisions. Examples include DSDV and OLSR. In contrast, a reactive routing protocol only establishes and maintains a route when it is actually needed, i.e. ondemand.This is typically done using an explicit route discovery process. Examples of such protocols include AODV and DSR.

主动路由协议在实际需要之前建立和维护路由信息（通常以表的形式）。这允许节点快速做出路由决策。示例包括 DSDV 和 OLSR。相反，反应路由协议仅在实际需要时（即按需）建立和维护路由。这通常使用显式路由发现过程完成。此类协议的示例包括 AODV 和 DSR。

Consider the following WSN scenarios and explain why you would choose either a proactive or a reactive routing solution:（请考虑以下 WSN 方案，并解释为什么选择主动路由解决方案或被动路由解决方案：）

(a) A WSN is used to monitor air pollution in a city where every sensor reports its sensor data once every minute to a single remote base station. Most sensors are mounted on lamp posts, but some are also mounted on city buses.

答：Because communication is frequent, a proactive approach may be appropriate. The routing protocol will ensure that table entries are updated whenever the topology changes, which are infrequent events since most radios are mounted on lamp posts.

由于沟通频繁，因此采取主动路由协议可能更合适。主动路由协议将确保每当拓扑更改时更新表条目。

(b) A WSN is used to measure humidity in a field, where low-power sensors report measurements only when certain thresholds are exceeded.

答：In this example, sensor communications will be infrequent, therefore routing information will only be needed occasionally. The cost of maintaining routing tables may cost too much energy, therefore a reactive solution may be more appropriate. The type of sensor data (humidity) indicates that latency is not a concern, which also justifies the use of a route discovery phase.

传感器节点通信不频繁，因此仅偶尔需要路由信息。维护路由表的成本可能花费太多能源，因此被动路由协议可能更合适。

© A WSN is used to detect the presence of vehicles, where each sensor locally records the times of vehicle detection. These records are delivered to the base station only when the sensor is explicitly queried.

答：Again, communication in such a network is infrequent and a sensor can establish a route whenever needed (i.e. when a query is issued) instead of continuously maintaining accurate table entries.

被动路由协议可能更合适，原因如上（b）。

What is datacentric routing? Why is datacentric routing feasible (or even necessary) compared to routing based on identities (addresses)?

答：If the focus is on the data generated by sensors and not the identity of the sensors generating these data, then we call a routing protocol datacentric. For example, if sensor data describing the environmental temperature must be routed to all sinks interested in such data, irrelevant of the data originator (i.e. which sensors produced the data), the focus is on the gathered data itself.

若在路由时，相比节点信息我们更关注节点传输的数据，那就成为以数据为中心的路由。 例如，如果描述环境温度的传感器数据必须路由到对此类数据感兴趣的所有接收器，与数据创建者无关（即哪个传感器生成数据），则重点将放在收集的数据本身上。 这在一些情况下是必要的。

For the network topology shown in Figure 7.22, identify the optimal routes for source A to sink M according to the following criteria (describe how you compute the cost for the optimal route). The numbers X/Y along each link indicate the latency (X) and energy cost (Y) for transmitting a single packet over the link. The number Z under each node indicates the node’s remaining energy capacity. (每个链路上的数字 X/Y 表示通过链路传输单个数据包的延迟 （X） 和能量成本 （Y）。每个节点下的数字 Z 表示节点的剩余能量。)

请找出使用下列策略的最优路径 (a) Minimum number of hops

答：The minimum hop route is AEGJM, which requires 4 hops (3 relay nodes).

(b) Minimum energy consumed per packet

答：The route with the minimum energy consumer per packet is route AEFGHKM. The energy cost for this transmission from A to M is 2+1+1+2+1+2=9.

© Maximum average energy capacity (eliminate hops that would result in a higher average but unnecessarily add to the route length!)

答：The route with the maximum average energy capacity would be AEGHKM. The maximum average energy capacity for this route = (7+4+6+5)/4 = 5.5.

(d) Maximum minimum energy capacity

答：The route with the maximum minimum energy capacity would be AEGHKM (the same as the maximum average energy capacity). The minimum energy capacity on this route is 4 (node G).

(e) Shortest latency

答：The shortest latency route would be AEGJLM and the total latency for this route is 9.

Flooding is a simple strategy for distributing data to one specific or all sensor nodes in a network. Answer the following questions:

(a) Explain the three challenges of flooding described in this chapter.

答：A node receiving a packet forwards this packet to all neighbors regardless of whether these neighbors have already received a copy of this packet. This is known as the implosion problem. The redundancy in sensor data from sensors that monitor similar physical environments is known as the overlap problem. Finally, flooding does not consider the resources available on all nodes, i.e. it is resourceblind.

（1）接收数据包的节点将此数据包转发给所有邻居，而不管这些邻居是否已收到此数据包的副本。这一问题称为implosion problem。 （2）来自监控相似物理环境的传感器的数据产生的冗余问题。这一问题称为overlap problem。 （3）泛洪时不考虑所有节点上的可用资源。这一问题称为resourceblind。

(b) Which one(s) of these are addressed by gossiping and how are they addressed?

答：Gossiping addresses only the implosion problem, i.e. it uses a probabilistic approach to decide whether to forward data or not.

只解决implosion problem，使用概率来决定是否转发。

© For the topologies shown in Figure 4 and Figure 5, what are good choices for the maximum hop count? Explain your answer. 答：In both networks, a good choice for a maximum hop count would be 8. The maximum hop count should be chosen large enough that every node can reach any other node in the network, but not too large to avoid packets from traveling too long (e.g. particularly in networks where a packet could travel in circles).

上面两张图的最大跳数最好都是8，这个数要足够大，满足任意两个节点都可在该跳数内找到连接。但不能太大以避免过度转发。（上面两个图中，距离最远的点之间需要8跳连接）

(d) How do sequence numbers contribute to reducing unnecessary transmissions? Are sequence numbers alone sufficient and if not, what other information is needed to use them correctly?

答：Sequence numbers allow nodes to distinguish packets from each other, i.e. to identify new packets or duplicates. Sequence numbers alone are typically not enough, they need to be combined with other information, such as the identity of the sender. Only then can a packet be identified uniquely.

序列号允许节点区分数据包彼此，即识别新数据包或重复。单是序列号通常是不够的，它们需要与其他信息（如发送节点的标识）组合使用。只有这样，才能唯一地标识数据包。

How does the SPIN family of protocols address the three challenges faced by flooding? What are the disadvantages of a negotiationbased protocol such as SPIN?

答：SPIN uses two techniques to address these challenges. First, to address implosion and overlap, SPIN nodes negotiate with their neighbors before they transmit. Second, to address resource blindness, SPIN uses a resource manager on each node, which keeps track of actual resource consumption and allowing the nodes to adapt routing and communication behavior based on resource availability. A problem with the negotiationbased approach is that it introduces a significant amount of control overhead, i.e. the cost of extra control messages could outweigh the benefits of SPIN in some scenarios. The negotiationbased approach also introduces additional delays into the communications.

SPIN 使用两种技术来应对这些挑战。 （1）解决implosion problem和overlap problem 策略是在传输之前，SPIN 先与邻居协商。 （2）解决resourceblind问题 策略是在每个节点上使用资源管理器，从而保持跟踪实际资源消耗，并允许节点调整路由和行为。

基于协商的SPIN协议缺点是协商时引入了大量的控制开销，甚至有时会超过其好处。同时，基于谈判的协议会带来额外的时延。

Explain the concept of directed diffusion. Can you imagine at least three strategies or goals for reinforcement?

答：In directed diffusion, nodes request data by sending interests for named data to other nodes in the network. These interests are disseminated throughout the network and gradients are established that are used to direct sensor data back to the originator of the interest. Reinforcement is used to strengthen some gradients in the network based on some goals or metric. For example, a node could reinforce a neighbor from which the sink has received a previously unseen event, a neighbor that appears to have large energy capacity, or a neighbor that shares a very reliable link with this node.

在定向扩散中，节点通过向网络中的其他节点发送命名数据的兴趣来请求数据。这些兴趣在整个网络中传播，并建立梯度，用于将传感器数据引导回请求方。

In AODV, is it possible that route discovery packets travel in the network forever? Why or why not?

答：Each node is identified by its source and a sequence number (broadcast ID), allowing forwarding nodes to discard duplicate packets. Further, most routing protocols use timetolive values (maximum number of hops a packet travels) to prevent a packet from traveling in the network for too long.

每个节点由其源和序列号（广播 ID）标识，允许转发节点丢弃重复的数据包。此外，大多数路由协议设置TTL生存时间（数据包传输的最大跳数）来防止数据包在网络中传输时间过长。

Consider the topology in Figure 7.26. Node A wishes to forward a packet toward destination L via one of its neighbors (its communication range is indicated with the circle). Which neighbor will A choose with each of the following forwarding strategies: (a) greedy forwarding（减少到G的最短距离）

答：G minimizes the distance to the destination L.

(b) nearest with forwarding progress（找最近但增益的）

答：Node E makes positive progress towards L, but is also the nearest neighbor.

© most forwarding progress within radius（找增益最大的）

答：G also makes the most forwarding progress within A’s transmission radius.

(d) compass routing（找夹角最小的）

答：F is A’s neighbor with the smallest angle between the line connecting the source and the destination and the line connecting the source with the neighbor.

Why is time synchronization needed in a WSN? Name at least three concrete examples.

答：Time synchronization is needed to achieve accurate temporal correlation of observed events, e.g. to detect the speed of a moving object. Time synchronization is also needed for many MAClayer protocols, e.g. to accurately determine when a node can transmit in a TDMAbased system. Finally, many networks utilize duty cycling, i.e. devices are awake for brief periods of time and sleep otherwise. Accurate timing information is needed to determine when a node has to turn its radio back on.

（1）有时需要时钟同步实现信号监测 如速度监测。 （2）有些MAC层协议需要时钟同步 如确定节点何时可以在基于 TDMA 的系统中传输。 （3）有些许多网络使用占空比循环 即短暂苏醒然后进入长时间睡眠，需要时钟同步通知节点何时苏醒打开无线电。

Explain the difference between external and internal time synchronization and name at least one concrete example for each type of synchronization.

答：External synchronization means that the clocks in a network are synchronized with an external source of time (reference clock). For example, GPS can be used to achieve external synchronization. Internal synchronization refers to the process of synchronizing the clocks of sensor nodes in a networkwith each other,without the support of an external reference clock. To achieve internal synchronization, sensor nodes could elect a master node which periodically broadcasts its time to all other nodes in the network, allowing them to reset their clocks to correct for any drifts.

外部同步意味着网络中的时钟与外部时间源（参考时钟）同步。例如，GPS 可用于实现外部同步。 内部同步是指在不受外部参考时钟支持的情况下，将网络中传感器节点的时钟相互同步的过程。为了实现内部同步，传感器节点可以选择一个主节点，该主节点会定期将其时间广播到网络中的所有其他节点，从而允许它们重置时钟以纠正任何时间误差。

Describe the reasons for nondeterminism of communication latencies and why this nondeterminism affects time synchronization.（描述通信延迟的不可确定性的原因，以及这种非确定性影响时钟同步的原因。）

答：There are four main contributors to nondeterminism of communication latencies: （1）send delays （2）access delays （3）propagation delays （4）receive delays Since these delays can depend on a variety of parameters, including the distance between nodes, system call interface latencies, context switches, and characteristics of the MAC protocol, the measurement of offsets and delays will be inaccurate, thereby affecting the quality of time synchronization.

通信延迟的确定性有四个主要因素：发送延迟、访问延迟、传播延迟和接收延迟。由于这些延迟可能依赖于各种参数，包括节点之间的距离、系统呼叫接口延迟、上下文切换和 MAC 协议的特征，因此偏移量和延迟的测量将不准确，因此影响时钟同步的质量。

Why is localization needed in wireless sensor networks? Name at least two concrete scenarios or applications where localization is required.

答：Sensor nodes are often deployed in an adhoc fashion, without knowledge of their exact deployment position. Localization is then necessary to provide a physical context to sensor readings, i.e. most sensor readings are meaningless without knowledge of where the readings were obtained. For example, localization is required in sensor network that detects wild fires to ensure that firefighters can quickly locate the affected areas and to predict the spread of the wild fire. Similarly, in surveillance applications, location information is required to be able to guide law enforcement officers quickly towards an intruder.

传感器节点通常以临时方式部署，而不知道它们的确切部署位置。 定位是必要的，以提供一个物理上下文的传感器读数，否则大多数传感器读数是毫无意义的，不知道读数在哪里获得。 例如，检测野火的传感器网络需要定位，以确保消防员能够快速定位受影响区域并预测野火的蔓延。 同样，在监视应用中，需要提供位置信息，以便能够引导执法人员快速接近入侵者。

Define the terms anchorbased localization and rangebased localization.

答：Anchorbased localization refers to the use of reference nodes (anchors) with wellknown locations. Communication between sensor nodes and these anchors can be used to estimate the locations of the sensors. Rangebased localization estimate locations based on range measurements, i.e. measurements of the distances between nodes.

基于锚点的定位是指使用具有已知位置的参考节点（锚点）。传感器节点与这些锚点之间的通信可用于估计传感器的位置。 基于范围的定位基于范围测量估计位置，即节点之间的距离测量。

What is the main disadvantage for both TDoA and AoA ranging techniques?

名词解释：

Time of Arrival（ToA）：用已知载体速度（如声速）乘以到达目标的时间得到距离。

Time Difference of Arrival（TDOA）：使用两种信号作为载体，计算式为 d i s t = ( v 1 − v 2 ) ∗ ( Δ a r r i v e − Δ s e n d ) dist=(v_{1}-v_{2})*(\Delta_{arrive}-\Delta_{send}) dist=(v1​−v2​)∗(Δarrive​−Δsend​)

Angle of Arrival（AoA）：确定信号传播的方向，测量信号传播方向与标准方向的夹角，通常使用天线或麦克风阵列。

答：Both techniques requires extra hardware (e.g. two radios for TDoA and an array of antennas for AoA), which may be infeasible for many lowcost and lowpower sensor networks.

这两种技术都需要额外的硬件（例如 TDoA 的两个无线电和 AoA 的天线阵列），对于许多低成本和低功率传感器网络来说，这可能不可行。

答：

Explain the concept of GPS localization and answer the following questions:

(a) Why are three satellites enough to obtain a position on the globe?

答：Even though the use of three satellites leads to two intersection points of the three spheres, one of these two intersection points can typically be eliminated easily, e.g., because it would place the receiver device far out in space or deep below the ground.

即使使用三颗卫星会导致三个球体的两个交叉点，但通常很容易消除这两个交叉点中的一个，例如，它将接收器装置放置在远离空间或深于地面的地方。

(b) Why is it preferred to have at least four satellites available for localization?

答：A fourth satellite allows to obtain a more accurate location. This is due to the stringent time synchronization requirements, i.e. receiver devices and satellites are supposed to be tightly synchronized.However, the receiver clocks aremuch simpler and cheaper than the clocks in the satellites, thereby leading to synchronization and consequently also to localization errors. The fourth sphere should ideally intersect the other three spheres at the exact location of the receiver. Because of the timing errors, this may not be the case. If the spheres are too large to obtain an intersection point, their sizes can be reduced by adjusting the clock until the spheres are small enough to intersect in one point (and similarly we can address the case where spheres are too small). This is possible because the timing errors are the same for all measurements and a receiver can calculate the required clock adjustment to obtain a single intersection point. Finally, a fourth satellite also allows the receiver to obtain a measurement for the elevation.

使用四颗卫星可以获得更准确的位置。这是由于严格的时间同步要求，即接收器设备和卫星应该紧密同步（光信号传播需要时间，会带来时钟不一致问题）。然而，接收时钟比卫星中的时钟简单得多，成本更低，从而导致同步，进而导致定位错误。第四个球体最好与接收器的确切位置的其他三个球体相交。由于计时错误，情况可能并非如此。如果球体太大而无法获得交点，则可以通过调整时钟来减小其大小，直到球体足够小，以在一个点中相交（同样，我们可以解决球体太小的情况）。这是可能的，因为所有测量的时序误差都相同，并且接收器可以计算所需的时钟调整以获得单个交点。最后，第四颗卫星还允许接收器获得高度的测量值。

© What is the purpose of the monitor stations and the master control station?

答：The monitor stations constantly receive the data sent by the satellites and forward this information to a master control station (MCS). The MCS uses this information to compute corrections to the satellites’ orbital and clock information, which are then sent back to the appropriate satellites via ground antennas.

监测站不断接收卫星发送的数据，并将此信息转发到主控制站 （MCS）。MCS利用这些信息计算对卫星轨道和时钟信息的修正，然后通过地面天线将这些信息发回适当的卫星。

(d) Why is typically not feasible to have all wireless sensor nodes equipped with a GPS receiver?

答：GPS receiver are both costly and energyhungry devices, which may make them unsuitable for use in lowpower and lowcost sensor networks.

GPS 接收器既昂贵又耗费能源，可能不适合用于低功耗和低成本传感器网络。

已知A1到A2距离40m，A1到A3距离110m，A2到A3距离35m。 那么估计灰色节点到三个点之间的距离。

先计算每个节点的两条邻边上平均每跳距离是多少。 A 1 ： ( 40 + 110 ) ÷ ( 2 + 5 ) = 21.43 A1：(40+110)\div(2+5)=21.43 A1：(40+110)÷(2+5)=21.43 A 2 ： ( 40 + 35 ) ÷ ( 2 + 3 ) = 15 A2：(40+35)\div(2+3)=15 A2：(40+35)÷(2+3)=15 A 3 ： ( 110 + 35 ) ÷ ( 5 + 3 ) = 18.125 A3：(110+35)\div(5+3)=18.125 A3：(110+35)÷(5+3)=18.125

由于灰色节点距离A1为2跳，距离A2为2跳，距离A3为3跳。 因此我们可以使用A1或A2上的平均每跳距离。

若使用A2上的平均每跳距离，则距离

A1 为 2 × 15 = 30 m 2\times15=30m 2×15=30m A2 为 2 × 15 = 30 m 2\times15=30m 2×15=30m A3 为 3 × 15 = 45 m 3\times15=45m 3×15=45m

A sensor node in a WSN using the lighthouse approach for localization detects the first beam of light at time 0 s and the second beam of light at time 0.25 s. The next time the first beam of light is detected is 7 s. The distance of the two light sources (beam width) is 10 cm. What is the distance of the sensor to the light emitter?

答：The distance is computed as: d = b 2 s i n ( α / 2 ) d=\frac{b}{2sin(\alpha/2)} d=2sin(α/2)b​ where α is computed as: α = 2 π t b e a m t t u r n \alpha=2\pi\frac{t_{beam}}{t_{turn}} α=2πtturn​tbeam​​ thus α = 2 π × 0.25 7 = 0.224 \alpha=2\pi\times\frac{0.25}{7}=0.224 α=2π×70.25​=0.224 d = 10 c m 2 s i n ( 0.224 / 2 ) = 25.6 m . d=\frac{10cm}{2sin(0.224/2)}=25.6 m. d=2sin(0.224/2)10cm​=25.6m.